#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : Subsets2.py
# @Time    : 2020/9/5 13:27
# @Description:
from typing import List


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
        Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

        Note: The solution set must not contain duplicate subsets.

        Example:
            Input: [1,2,2]
            Output:
            [
              [2],
              [1],
              [1,2,2],
              [2,2],
              [1,2],
              []
            ]

        :param nums:
        :return:
        """
        nums.sort()
        output = [[]]
        for num in nums:
            output += [curr + [num] for curr in output if curr + [num] not in output]
        return output


if __name__ == '__main__':
    S = Solution()
    nums = [4, 4, 4, 1, 4]
    # nums = [1, 2, 2]
    print(S.subsetsWithDup(nums))
    print('done')
